package ev.operator;//need to add this line

import ev.data.*;//need to add this line
import java.util.ArrayList;
import java.util.Random;


public class edgecross implements Crossover{
	public	ArrayList<Individual> cross(Individual a, Individual b){
		ArrayList<Individual> res = new ArrayList<Individual>();
		int[] parent1 = a.getList();
		int[] parent2 = b.getList();
		Random r = new Random();
		int len = parent1.length;
		//System.out.println(len);
		int[] child = new int[len];
		int[][] table = new int[len][5];
		for(int i = 0; i < len; i++){
			if(i == 0){
				table[parent1[i]-1][0] = parent1[len-1];
				table[parent1[i]-1][1] = parent1[i+1];
			}
			else if(i == len-1){
				table[parent1[i]-1][0] = parent1[0];
				table[parent1[i]-1][1] = parent1[i-1];
			}
			else{
				table[parent1[i]-1][0] = parent1[i-1];
				table[parent1[i]-1][1] = parent1[i+1];
			}
			table[i][4] = 4;
		}
		for(int i = 0; i < len; i++){
			if(i == 0){
				table[parent2[i]-1][3] = parent2[len-1];
				table[parent2[i]-1][2] = parent2[i+1];
			}
			else if(i == len-1){
				table[parent2[i]-1][3] = parent2[0];
				table[parent2[i]-1][2] = parent2[i-1];
			}
			else{
				table[parent2[i]-1][3] = parent2[i-1];
				table[parent2[i]-1][2] = parent2[i+1];
			}
			if(table[parent2[i]-1][3] == table[parent2[i]-1][0] ||
					table[parent2[i]-1][3] == table[parent2[i]-1][1]){
				table[parent2[i]-1][3] += len;
				table[parent2[i]-1][4]--;
			}
			if(table[parent2[i]-1][2] == table[parent2[i]-1][0] ||
					table[parent2[i]-1][2] == table[parent2[i]-1][1]){
				table[parent2[i]-1][2] += len;
				table[parent2[i]-1][4]--;
			}
		}
	    child[0] = r.nextInt(len)+1;
		//System.out.println(res[0]);
		for(int i = 1; i < len; i++){
			int id = child[i-1]-1;
			boolean plus = false;
			int saveid = 0 ;
			for(int j = 0; j < 4; j++){
				if(table[id][j]>len){
					plus  = true;
					saveid = j;
					continue;
				}
				if(table[id][j] != 0){
					for(int k = 0; k < 4; k++){
						if(table[table[id][j]-1][k] == child[i-1]
						             || table[table[id][j]-1][k] == child[i-1]+len){
							table[table[id][j]-1][k] = 0;
						}
					}
				}
			}
			if(plus){
				child[i] = table[id][saveid] - len;
				table[id][saveid] = 0;
				if(table[id][0] == child[i])
					table[id][0] = 0;
				else
					table[id][1] = 0;
				//System.out.println(res[i]+"plus");
				continue;
			}
			int shortlist = 5;
			int times = 0;
			int[] candidate = new int[4];
			for(int j = 0; j < 4; j++){
				if(table[id][j] == 0)
					continue;
				if(table[table[id][j]-1][4] < shortlist){
					shortlist = table[table[id][j]-1][4];
					candidate[0] = j;
					times = 1;
				}
				else if(table[table[id][j]-1][4] == shortlist){
					candidate[times] = j;
					times++;
				}
			}
			if(times == 1){
				child[i] = table[id][candidate[0]];
				//System.out.println(res[i]+"shortest list");
			}
			if(times>1){
				int tmp = r.nextInt(times);
				child[i] = table[id][candidate[tmp]];
				//System.out.println(res[i]+"random choice");
			}

		}
		Individual child1 = new Individual(child);
		res.add(child1);
		return res;
	}
}
